/*
 * $Id: GarbageFreeFormatterUtils.java 131 2013-01-23 05:48:57Z vladimirow@mail.ru $
 * $HeadURL: http://ultralog.googlecode.com/svn/ultralog/tags/release-20130123/src/java/com/google/code/ultralog/formatter/gfree/GarbageFreeFormatterUtils.java $
 *
 * This file is a part of ultralog project (http://code.google.com/p/ultralog/).
 * Released under New BSD License.
 */
package com.google.code.ultralog.formatter.gfree;

import java.util.Arrays;

import com.google.code.ultralog.utils.CharacterOutputStream;

/**
 * Contains various useful methods that simplify implementation of garbage-free
 * formatters.
 *
 * @author Mikhail Vladimirov
 */
public class GarbageFreeFormatterUtils
{
    private final static int [] DIGITS = new int [10000];

    static
    {
        for (int i = 0; i < 10000; i++)
        {
            DIGITS [i] =
                (('0' + i / 1000 % 10) << 24) +
                (('0' + i / 100 % 10) << 16) +
                (('0' + i / 10 % 10) << 8) +
                (('0' + i / 1 % 10) << 0);
        }
    }

    private final static int BUFFER_SIZE = 20;

    private final static ThreadLocal <char []> CHAR_BUFFER =
        new ThreadLocal <char[]> ()
        {
            @Override
            protected char[] initialValue ()
            {
                return new char [BUFFER_SIZE];
            }
        };

    /**
     * Write integer value in decimal format to given character output stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeInteger (int value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        if (value == Integer.MIN_VALUE)
            output.write ("-2147483648", 0, 11);
        else if (value == 0)
            output.write ('0');
        else
        {
            boolean sign = value < 0;
            value = Math.abs (value);

            char [] buffer = CHAR_BUFFER.get ();
            int pos = BUFFER_SIZE;

            while (value >= 10000)
            {
                int v = value / 10000;
                int d = value - v * 10000;
                value = v;

                int d4 = DIGITS [d];

                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);
            }

            int d4 = DIGITS [value];

            if (value >= 1)
                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);

            if (value >= 10)
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);

            if (value >= 100)
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);

            if (value >= 1000)
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);

            if (sign)
                buffer [--pos] = '-';

            output.write (buffer, pos, BUFFER_SIZE - pos);
        }
    }

    /**
     * Write long value in decimal format to given character output stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeLong (long value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        if (value == Long.MIN_VALUE)
            output.write ("-9223372036854775808", 0, 20);
        else if (value == 0L)
            output.write ('0');
        else
        {
            boolean sign = value < 0;
            value = Math.abs (value);

            char [] buffer = CHAR_BUFFER.get ();
            int pos = BUFFER_SIZE;

            while (value > Integer.MAX_VALUE)
            {
                long v = value / 10000;
                int d = (int)(value - v * 10000);
                value = v;

                int d4 = DIGITS [d];

                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);
            }

            int intValue = (int)value;

            while (intValue >= 10000)
            {
                int v = intValue / 10000;
                int d = intValue - v * 10000;
                intValue = v;

                int d4 = DIGITS [d];

                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);
            }

            int d4 = DIGITS [intValue];

            if (intValue >= 1)
                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);

            if (intValue >= 10)
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);

            if (intValue >= 100)
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);

            if (intValue >= 1000)
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);

            if (sign)
                buffer [--pos] = '-';

            output.write (buffer, pos, BUFFER_SIZE - pos);
        }
    }

    /**
     * Write float value in simple decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeFloat (float value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeFloat (value, output, false);
    }

    /**
     * Write float value in scientific decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeFloatScientific (
        float value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeFloat (value, output, true);
    }

    /**
     * Write double value in simple decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeDouble (double value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeDouble (value, output, false);
    }

    /**
     * Write double value in scientific decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeDoubleScientific (
        double value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeDouble (value, output, true);
    }

    private final static int BUFFER_LENGTH = 81;

    // log_2 (10)
    private final static double EXPONENT_FACTOR =
        3.3219280948873623478703194294894;

    private final static int [] POWER_5 = {
        1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625,
        48828125, 244140625, 1220703125};

    private final static int [] POWER_10 = {
        1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
        1000000000};

    private final static ThreadLocal <int []> BUFFER =
        new ThreadLocal <int []> ()
        {
            @Override
            protected int[] initialValue()
            {
                return new int [BUFFER_LENGTH];
            };
        };

    private static void writeFloat (
        float value, CharacterOutputStream output, boolean scientific)
    {
        if (Float.isNaN (value))
            output.write ("NaN", 0, 3);
        else if (Float.isInfinite (value))
        {
            if (value > 0.0f)
                output.write (
                    "Infinity",
                    0, 8);
            else
                output.write (
                    "-Infinity",
                    0, 9);
        }
        else
        {
            int bits = Float.floatToRawIntBits (value);

            boolean negative = bits >>> 31 != 0;
            int binaryExponent = ((bits >>> 23) & 0xFF) - 150;
            int binaryMantissa = bits & 0x7FFFFF;

            if (binaryExponent == -150) // Subnormal mantissa
                binaryExponent = -149;
            else // Normal mantissa
                binaryMantissa += 0x800000;

            double significantDigits = (binaryExponent - 1) / EXPONENT_FACTOR;
            int decimalExponent =
                (int)Math.floor (significantDigits);
            int margin = (int)Math.floor (
                Math.pow (10.0, significantDigits - decimalExponent));

            long decimalMantissa = getDecimalMantissa (
                binaryMantissa, binaryExponent, decimalExponent);

            int lastDigit = (int)(decimalMantissa % 10);

            if (lastDigit <= margin)
            {
                decimalMantissa /= 10;
                decimalExponent += 1;
            }
            else if (lastDigit >= 10 - margin)
            {
                decimalMantissa = decimalMantissa / 10 + 1;
                decimalExponent += 1;
            }

            if (scientific)
                formatScientific (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
            else
                formatSimple (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
        }
    }

    private static void writeDouble (
        double value, CharacterOutputStream output, boolean scientific)
    {
        if (Double.isNaN (value))
            output.write ("NaN", 0, 3);
        else if (Double.isInfinite (value))
        {
            if (value > 0.0f)
                output.write (
                    "Infinity",
                    0, 8);
            else
                output.write (
                    "-Infinity",
                    0, 9);
        }
        else
        {
            long bits = Double.doubleToRawLongBits (value);

            boolean negative = bits >>> 63 != 0;
            int binaryExponent = (int)((bits >>> 52) & 0x7FF) - 1075;
            long binaryMantissa = bits & 0xFFFFFFFFFFFFFL;

            if (binaryExponent == -1075) // Subnormal mantissa
                binaryExponent = -1074;
            else // Normal mantissa
                binaryMantissa += 0x10000000000000L;

            double significantDigits = (binaryExponent - 1) / EXPONENT_FACTOR;
            int decimalExponent =
                (int)Math.floor (significantDigits);
            int margin = (int)Math.floor (
                Math.pow (10.0, significantDigits - decimalExponent));

            long decimalMantissa = getDecimalMantissa (
                binaryMantissa, binaryExponent, decimalExponent);

            int lastDigit = (int)(decimalMantissa % 10);

            if (lastDigit <= margin)
            {
                decimalMantissa /= 10;
                decimalExponent += 1;
            }
            else if (lastDigit >= 10 - margin)
            {
                decimalMantissa = decimalMantissa / 10 + 1;
                decimalExponent += 1;
            }

            if (scientific)
                formatScientific (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
            else
                formatSimple (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
        }
    }

    private static void formatSimple (
            boolean negative, long decimalMantissa, int decimalExponent,
            CharacterOutputStream output)
    {
        if (decimalMantissa < 0)
            throw new IllegalArgumentException (
                "Decimal mantissa (" + decimalMantissa + ") < 0");

        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        if (negative)
            output.write ('-');

        if (decimalMantissa == 0)
            output.write ("0.0", 0, 3);
        else
        {
            while (decimalMantissa % 10 == 0)
            {
                decimalMantissa /= 10;
                decimalExponent += 1;
            }

            if (decimalExponent >= 0)
            {
                writeLong (decimalMantissa, output);
                writeCharacterNTimes ('0', decimalExponent, output);
                output.write (".0", 0, 2);
            }
            else // decimalExponent < 0
            {
                int fdc = 1;
                int dc = 1;

                long m = decimalMantissa;
                long k = 1L;
                for (int i = 0; m > 0; i++, m /= 10)
                {
                    if (i < -decimalExponent)
                    {
                        k *= 10;

                        if (m % 10 != 0)
                            fdc = i + 1;
                    }

                    dc = i + 1;
                }

                if (dc <= -decimalExponent) // No significant digits before dot
                {
                    output.write ("0.", 0, 2);
                    writeCharacterNTimes ('0', -decimalExponent - dc, output);
                    writeLong (decimalMantissa, output);
                }
                else
                {
                    writeLong (decimalMantissa / k, output);
                    output.write ('.');
                    writeCharacterNTimes ('0', -decimalExponent - fdc, output);
                    writeLong (decimalMantissa % k, output);
                }
            }
        }
    }

    private static void formatScientific (
            boolean negative, long decimalMantissa, int decimalExponent,
            CharacterOutputStream output)
    {
        if (decimalMantissa < 0)
            throw new IllegalArgumentException (
                "Decimal mantissa (" + decimalMantissa + ") < 0");

        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        int n = -1;
        long m = decimalMantissa;
        while (m > 0)
        {
            n += 1;
            m /= 10;
        }

        if (n < 0) n = 0;

        formatSimple (negative, decimalMantissa, - n, output);

        output.write ('e');

        writeInteger (decimalMantissa == 0 ? 0 : (decimalExponent + n), output);
    }

    private static long getDecimalMantissa (
        long binaryMantissa, int binaryExponent, int decimalExponent)
    {
        if (binaryMantissa < 0)
            throw new IllegalArgumentException (
                "Binary mantissa (" + binaryMantissa + ") < 0");

        if (binaryExponent < -1075)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") < -1075");

        if (binaryExponent > 1075)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") > 1075");

        if (binaryExponent == 0)
        {
            if (decimalExponent == 0)
                return binaryMantissa;
            else if (decimalExponent > 0)
            {
                long result = binaryMantissa;
                for (int i = 0; i < decimalExponent; i++)
                    result /= 10;
                return result;
            }
            else // decimalExponent < 0
            {
                long result = binaryMantissa;
                for (int i = 0; i > decimalExponent; i--)
                    result *= 10;
                return result;
            }
        }
        else if (binaryExponent > 0)
        {
            int [] buffer = BUFFER.get ();
            int pos = binaryExponent / 32;
            int offset = binaryExponent % 32;
            int l;

            if (offset > 0)
            {
                buffer [pos + 2] = (int)(binaryMantissa >>> (64 - offset));
                l = pos + 3;
            }
            else l = pos + 2;

            buffer [pos + 1] = (int)(binaryMantissa >>> (32 - offset));
            buffer [pos] = (int)(binaryMantissa << offset);

            Arrays.fill (buffer, 0, pos, 0);

            return normalizeDecimalMantissa (buffer, l, decimalExponent);
        }
        else // binaryExponent < 0
        {
            int [] buffer = BUFFER.get ();
            int l = (-binaryExponent * 7 / 3 + 95) / 32;

            buffer [0] = (int)binaryMantissa;
            buffer [1] = (int)(binaryMantissa >>> 32);

            Arrays.fill (buffer, 2, l, 0);

            int maxStep = POWER_5.length - 1;
            for (int i = 0; i > binaryExponent; )
            {
                int step = Math.min (i - binaryExponent, maxStep);
                int k = POWER_5 [step];

                long carry = 0;
                for (int j = 0; j < l; j++)
                {
                    long chunk = (((long)buffer [j]) & 0xFFFFFFFFL) * k + carry;

                    buffer [j] = (int)chunk;
                    carry = chunk >>> 32;
                }

                i -= step;
            }

            return normalizeDecimalMantissa (
                buffer, l, decimalExponent - binaryExponent);
        }
    }

    private static long normalizeDecimalMantissa (
        int [] buffer, int length, int decimalExponent)
    {
        if (buffer == null)
            throw new IllegalArgumentException ("Buffer is null");

        if (length < 2)
            throw new IllegalArgumentException ("Length (" + length + ") < 2");

        int bufferLength = buffer.length;
        if (length > buffer.length)
            throw new IllegalArgumentException (
                "Length (" + length + ") > buffer length (" +
                bufferLength + ")");

        if (decimalExponent > 0)
        {
            boolean increment = false;
            int maxStep = POWER_10.length - 1;
            for (int i = 0; i < decimalExponent; )
            {
                int step = Math.min (decimalExponent - i, maxStep);
                int k = POWER_10 [step];

                long carry = 0;
                for (int j = length - 1; j >= 0; j--)
                {
                    long chunk =
                        (carry << 32) + (((long)buffer [j]) & 0xFFFFFFFFL);
                    buffer [j] = (int)(chunk / k);
                    carry = (int)(chunk % k);

                    increment = carry > k / 2;
                }

                i += step;
            }

            if (increment)
            {
                for (int i = 0; i < length; i++)
                {
                    buffer [i] += 1;
                    if (buffer [i] != 0) break;
                }
            }
        }

        long result =
            (((long)buffer [1]) << 32 | (((long)buffer [0]) & 0xFFFFFFFFL));

        for (int i = 0; i > decimalExponent; i--)
            result *= 10;

        return result;
    }

    private static void writeCharacterNTimes (
            char ch, int n, CharacterOutputStream output)
       {
           if (n < 0) throw new IllegalArgumentException ("N < 0");

           if (output == null)
               throw new IllegalArgumentException ("Output is null");

           while (n > 0)
           {
               switch (n)
               {
               case 1:
                   output.write (ch);
                   n -= 1;
                   break;
               case 2:
                   output.write (ch, ch);
                   n -= 2;
                   break;
               case 3:
                   output.write (ch, ch, ch);
                   n -= 3;
                   break;
               default:
                   output.write (ch, ch, ch, ch);
                   n -= 4;
                   break;
               }
           }
       }
}
